/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 */
class Solution {

    public static void main(String[] args) {
        /*ListNode listNode11 = new ListNode(1);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(4);
        ListNode listNode21 = new ListNode(1);
        ListNode listNode22 = new ListNode(3);
        ListNode listNode23 = new ListNode(4);
        listNode11.next = listNode12;
        listNode12.next = listNode13;
        listNode21.next = listNode22;
        listNode22.next = listNode23;*/
        ListNode listNode11 = new ListNode(-9);
        ListNode listNode12 = new ListNode(3);
        ListNode listNode21 = new ListNode(5);
        ListNode listNode22 = new ListNode(7);
        listNode11.next = listNode12;
        listNode21.next = listNode22;
        ListNode listNode = mergeTwoLists(listNode11, listNode21);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 感觉到智商被碾压，很明显应该用递归，而不是遍历两个列表
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode head = null;
        ListNode listNode = null;
        while (l1 != null || l2 != null) {
            if (null != l1 && null != l2) {
                if (l1.val < l2.val) {
                    if (head == null) {
                        head = l1;
                        listNode = head;
                    } else {
                        listNode.next = l1;
                        listNode = listNode.next;
                    }
                    l1 = l1.next;
                } else {
                    if (head == null) {
                        head = l2;
                        listNode = head;
                    } else {
                        listNode.next = l2;
                        listNode = listNode.next;
                    }
                    l2 = l2.next;
                }
            } else if (null == l2) {
                if (null == listNode) {
                    listNode = l1;
                    return listNode;
                }
                listNode.next = l1;
                break;
            } else if (null == l1) {
                if (null == listNode) {
                    listNode = l2;
                    return listNode;
                }
                listNode.next = l2;
                break;
            }
        }
        return head;
    }
}

class ListNode {

    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}